package com.lw.leetcode.tree.c;

/**
 * Created with IntelliJ IDEA.
 * 2407. 最长递增子序列 II
 *
 * @author liw
 * @version 1.0
 * @date 2022/9/11 21:25
 */
public class LengthOfLIS {

    public static void main(String[] args) {
        LengthOfLIS test = new LengthOfLIS();

        // 5
        int[] nums = {4, 2, 1, 4, 3, 4, 5, 8, 15};
        int k = 3;

        // 4
//        int[] nums = {7, 4, 5, 1, 8, 12, 4, 7};
//        int k = 5;

        // 1
//        int[] nums = {1, 2};
//        int k = 1;

        // 2
//        int[] nums = {2, 2, 3, 1, 3};
//        int k = 3;

        int i = test.lengthOfLIS(nums, k);
        System.out.println(i);
    }

    private Node root = new Node(1, 100000);

    public int lengthOfLIS(int[] nums, int k) {
        int s = 0;
        for (int num : nums) {
            int max = getMax(Math.max(num - k, 1), num - 1, root) + 1;
            s = Math.max(s, max);
            setMax(num, max, root);
        }
        return s;
    }

    private void setMax(int var, int max, Node node) {
        if (node.max < max) {
            node.max = max;
        }
        if (node.st == node.end) {
            return;
        }
        int m = node.st + ((node.end - node.st) >> 1);
        if (var <= m) {
            if (node.left == null) {
                node.left = new Node(node.st, m);
            }
            setMax(var, max, node.left);
            return;
        }
        if (node.right == null) {
            node.right = new Node(m + 1, node.end);
        }
        setMax(var, max, node.right);
    }

    private int getMax(int st, int end, Node node) {
        if (st > end || node == null) {
            return 0;
        }
        if ((st == node.st && end == node.end)) {
            return node.max;
        }
        int m = node.st + ((node.end - node.st) >> 1);
        if (end <= m) {
            return getMax(st, end, node.left);
        }
        if (st > m) {
            return getMax(st, end, node.right);
        }
        return Math.max(getMax(st, m, node.left), getMax(m + 1, end, node.right));
    }

    private static class Node {
        private int st;
        private int end;
        private int max;
        private Node right;
        private Node left;

        public Node(int st, int end) {
            this.st = st;
            this.end = end;
        }
    }

}
